﻿#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
//手搓二叉树
#include"Binary.h"
Binary* StrBinarTree(int x)
{
	Binary* node = (Binary*)malloc(sizeof(Binary));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->left = NULL;
	node->right = NULL;
	node->val = x;
	return node;
}
//中序遍历
int PrevOrder(Binary* pq)
{
	if (pq == NULL)
	{
		printf("NULL ");
		return 0;
	}
	PrevOrder(pq->left);
	printf("%d ", pq->val);
	PrevOrder(pq->right);
}
//前序遍历
int MiddleOrder(Binary* pq)
{
	if (pq == NULL)
	{
		printf("NULL ");
		return 0;
	}
	printf("%d ", pq->val);
	MiddleOrder(pq->left);
	MiddleOrder(pq->right);
}
//后序遍历
int AfterOrder(Binary* pq)
{
	if (pq == NULL)
	{
		printf("NULL ");
		return 0;
	}
	
	AfterOrder(pq->left);
	AfterOrder(pq->right);
	printf("%d ", pq->val);
}
//层序遍历
void TreeLevelOrder(Binary* root)
{
	Que q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		Binary* front = QueueFront(&q);
		printf("%d ", front->val);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}
//节点个数
int  TreeSize(Binary* qp)
{
	if (qp == NULL)
	{
		return 0;
	}

	return TreeSize(qp->left) + TreeSize(qp->right) + 1;
}
//叶子节点个数
int TreeLeafSize(Binary* qp){
	if (qp == NULL)
	{
		return 0;
	}
	if (qp->left == NULL && qp->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(qp->left) + TreeLeafSize(qp->right) ;//错误点
}
//第K层的节点个数
int TreeKLevel(Binary* qp, int k)
{
	assert(k>0);
	if (qp == NULL)
	{
		return  0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevel(qp->left, k - 1) + TreeKLevel(qp->right, k - 1);
}
//bool isUnivalTree(struct TreeNode* root) {
//	if (root == NULL)
//		return true;
//	if (root->left && root->left->val != root->val)
//		return false;
//	if (root->right && root->right->val != root->val)
//		return false;
//	return isUnivalTree(root->left) && isUnivalTree(root->right);
//}
//销毁
void TreeDestroy(Binary* qp)
{
	if (qp == NULL)
	{
		return ;
	}
	TreeDestroy(qp->left);
	TreeDestroy(qp->right);
	free(qp);
}
//寻找val为x的节点
Binary* FindTree(Binary* qp, int x)
{
	if (qp == NULL)
	{
		return NULL;
	}
	if (qp->val == x)
	{
		return qp;
	}
	Binary* ret = NULL;
	if (ret=(FindTree(qp->left, x)))
	{
		return ret;
	}
	ret = NULL;
	if (ret = (FindTree(qp->right, x)))
	{
		return ret;
	}
	return NULL;
}
//判断是否是完全二叉树
int BinaryTreeComplete(Binary* root)
{
	Que q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		Binary* front = QueueFront(&q);
		if (front == NULL)
		{
			break;
		}
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		    QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		Binary* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
